// 二叉搜素树的中序遍历为递增序列

var treeToDoublyList = function (root) {
  // 若根节点为空，则直接返回
  if (!root) return null;
  // 初始化空节点 pre
  let head = null;
  let pre = head;
  // 转化为双向链表
  function dfs(cur) {
    // 当节点 cur 为空时，代表越过叶节点，直接返回
    if (cur === null) return;
    dfs(cur.left);
    // 构建链表
    // 当 pre 为空时，代表正在访问链表头节点，记为 head
    // 当 pre 不为空时，修改双向节点引用
    // 保存 cur
    if (pre !== null) {
      pre.right = cur;
    } else {
      head = cur;
    }
    cur.left = pre;
    pre = cur;
    dfs(cur.right);
  }
  dfs(root);
  // 构建循环链表
  // 进行头节点和尾节点的相互指向
  // 执行到最后，pre = cur 相当于是最后一个元素
  head.left = pre;
  pre.right = head;
  return head;
};
